package com.nan.leetcode;

import java.util.ArrayList;
import java.util.List;

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}
public class Test4 {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        //先访问根节点，此处的“访问”不是打印，而是插入result末尾
        result.add(root.val);
        //先递归处理左子树,此时会得到一个左子树的遍历结果的List，这个结果也要加入result；
        result.addAll(preorderTraversal(root.left));
        //递归处理右子树
        result.addAll(preorderTraversal(root.right));
        return result;
    }

    //给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
    //如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            //进入这个条件意味着，一定是p和q其中一个为空，一个不为空
            return false;
        }
        //都不为空树，先判定根节点是不是值相同
        if (p.val != q.val) {
            return false;
        }
        //根节点相同，再去分别遍历左子树和右子树
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    //给你两棵二叉树 root 和 subRoot。
    // 检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。
    // 如果存在，返回 true ；否则，返回 false 。
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }
        boolean ret = isSameTree(root, subRoot);
        if (ret) {
            return ret;
        }
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        if (leftHeight > rightHeight) {
            return 1 + leftHeight;
        }
        return 1 + rightHeight;
    }

    //给定一个二叉树，判断它是否是高度平衡的二叉树。
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        //当前树只有一个节点
        if (root.right == null && root.left == null) {
            return true;
        }
        //访问当前节点，计算左右子树的高度，并求差值
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        if ((leftHeight - rightHeight) > 1 || (leftHeight - rightHeight) < -1) {
            return false;
        }
        //再递归处理左右子树的情况，因为是任意节点的左右子树的高度差
        return isBalanced(root.left) && isBalanced(root.right);
    }


    //给你一个二叉树的根节点 root ， 检查它是否轴对称。
    //主要看左右子树是不是镜像关系：左右子树根节点的值是不是相等，&&
    // 左子树的左子树和右子树的右子树是不是镜像关系&&左子树的右子树和右子树的左子树是不是镜像关系

    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }
        return isMirror(root.left,root.right);
    }
    public boolean isMirror(TreeNode p,TreeNode q){
        if(p==null&&q==null){
            return true;
        }
        if(p==null||q==null){
            return false;
        }
        if(p.val!=q.val){
            return false;
        }
        return isMirror(p.left,q.right)&&isMirror(p.right,q.left);
    }
}